https://leetcode.cn/problems/unique-paths-iii/description/
//class Solution
//{
//    bool vis[21][21];
//    int sum;
//    int m, n;
//    int ret;
//    int dx[4] = { -1,1,0,0 };
//    int dy[4] = { 0,0,-1,1 };
//public:
//    int uniquePathsIII(vector<vector<int>>& grid)
//    {
//        m = grid.size(), n = grid[0].size();
//        int d1 = 0, d2 = 0;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == 0)
//                {
//                    ret++;
//                }
//                else if (grid[i][j] == 1)
//                {
//                    d1 = i, d2 = j;
//                }
//            }
//        }
//        ret += 2;
//        vis[d1][d2] = true;
//        dfs(grid, d1, d2, 1);
//        return sum;
//    }
//
//    void dfs(vector<vector<int>>& grid, int x, int y, int step)
//    {
//        if (grid[x][y] == 2)
//        {
//            if (step == ret)
//            {
//                sum++;
//            }
//            return;
//        }
//        for (int k = 0; k < 4; k++)
//        {
//            int i = x + dx[k];
//            int j = y + dy[k];
//            if (i >= 0 && i < m && j >= 0 && j < n && !vis[i][j] && grid[i][j] != -1)
//            {
//                vis[i][j] = true;
//                dfs(grid, i, j, step + 1);
//                vis[i][j] = false;
//            }
//        }
//        return;
//    }
//};

https://leetcode.cn/problems/path-with-maximum-gold/description/
//class Solution
//{
//    bool vis[16][16];
//    int m, n;
//    int sum = 0;
//    int dx[4] = { -1,1,0,0 };
//    int dy[4] = { 0,0,-1,1 };
//public:
//    int getMaximumGold(vector<vector<int>>& grid)
//    {
//        m = grid.size(), n = grid[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] != 0)
//                {
//                    vis[i][j] = true;
//                    dfs(grid, i, j, grid[i][j]);
//                    vis[i][j] = false;
//                }
//            }
//        }
//        return sum;
//    }
//
//    void dfs(vector<vector<int>>& grid, int x, int y, int path)
//    {
//        sum = max(path, sum);
//        for (int k = 0; k < 4; k++)
//        {
//            int i = x + dx[k];
//            int j = y + dy[k];
//            if (i >= 0 && i < m && j >= 0 && j < n && !vis[i][j] && grid[i][j] != 0)
//            {
//                vis[i][j] = true;
//                dfs(grid, i, j, path + grid[i][j]);
//                vis[i][j] = false;
//            }
//        }
//    }
//};